Much effort has, and is, being expended to improve the program instructions (object code) produced by compilers. Such improvements are generally referred to as optimizations and include a variety of techniques including: in-lining; loop unrolling; instruction reordering; and others. As used herein, the terms "optimize" and/or "optimization" refer to the improvement of the program instructions produced by a compiler to achieve enhanced execution performance of the resulting program. It is not intended that these terms imply that the program is modified to achieve an optimum or optimal set of program instructions, but instead only that a performance increase is obtained over the case wherein the optimizations are not performed.
Most of the optimization techniques developed to date require that the compiler have information regarding the dependencies between various storage locations used by the program. For example, a sequence of instructions in a C program may be as follows:
x=y+z; PA1 *p=*a+*b; PA1 q=y+z; PA1 (i) constructing sets of anti-alias information comprising the amalgamation of the complements of respective alias sets provided by a first stage of a compilation process, a shadow variable being assigned to each pointer induced alias; PA1 (ii) determining sets of inter-compilation unit alias information; PA1 (iii) determining refined sets of inter-compilation unit alias information by removing aliases included in the respective anti-alias sets; PA1 (iv) augmenting the determined sets of inter-compilation unit alias information to include shadow to shadow aliasing determined by adding any intersection of the refined sets of inter-compilation unit alias information for each shadow variable with the respective refined set of inter-compilation unit alias information; and PA1 (v) reducing the resulting augmented sets of inter-compilation unit alias information by removing alias information in the respective anti-alias information sets to obtain final sets of inter-compilation alias information. PA1 (i) constructing sets of anti-alias information [AntiAlias()] comprising the amalgamation of the complements of respective alias sets provided by a first stage of a compilation process, a shadow variable being assigned to each pointer induced alias; PA1 (ii) determining sets of inter-compilation unit alias information [ICUAlias()]; PA1 (iii) determining refined sets of inter-compilation unit alias information [RAlias()] from EQU RAlias(x)=ICAlias(x)-AntiAlias(x) PA1 (iv) determining final sets of inter-compilation unit alias information [FAlias()] from EQU FAlias(x)=ICAlias(x).orgate.{s.vertline.s is a shadow and RAlias(s).andgate.RAlias(x).noteq.NULL})-AntiAlias(x) PA1 computer readable program code means for constructing sets of anti-alias information comprising the amalgamation of the complements of respective alias sets provided by a first stage of a compilation process, a shadow variable being assigned to each pointer induced alias; PA1 computer readable program code means for determining sets of inter-compilation unit alias information; PA1 computer readable program code means for determining refined sets of inter-compilation unit alias information by removing aliases included in the respective anti-alias sets; PA1 computer readable program code means for augmenting the determined sets of inter-compilation unit alias information to include shadow to shadow aliasing determined by adding any intersection of the refined sets of inter-compilation unit alias information for each shadow variable with the respective refined set of inter-compilation unit alias information; and PA1 computer readable code means for reducing the resulting augmented sets of inter-compilation unit alias information by removing alias information in the respective anti-alias information sets to obtain final sets of inter-compilation alias information. PA1 (i) constructing sets of anti-alias information [AntiAlias()] comprising the amalgamation of the complements of respective alias sets provided by a first stage of a compilation process, a shadow variable being assigned to each pointer induced alias; PA1 (ii) determining sets of inter-compilation unit alias information [ICUAlias()]; PA1 (iii) determining refined sets of inter-compilation unit alias information [RAlias()] from EQU RALias(x)=ICAlias(x)-AntiAlias(x) PA1 (iv) determining final sets of inter-compilation unit alias information [FAlias()] from EQU FAlias(x)=ICAlias(x).orgate.{s.vertline.s is a shadow and RAlias(s).andgate.RAlias(x).noteq.NULL})-AntiAlias(x)
It may be that, on the specific processor for which this C program is being compiled, a performance improvement can be obtained if the ordering of the last two statements is reversed so that y+z is only calculated once and is assigned to both x and q. However, without additional information, the compiler cannot reverse the ordering of the last two instructions as it is possible that the pointer p in fact points to y or z, and thus is intended to change the value of y or z before the assignment of the value of y+z to q, or that a or b point to q, which has previously had a value assigned to it and thus the value of y+z cannot be assigned to q before the value *a+*b is assigned through p.
Generally, a symbol (storage location or a variable) which may share storage with another symbol is referred to as an "alias" of, or is said to be "aliased with", the other symbol. Determining which symbols are aliased with which other symbols is very important when attempting to optimize object code as such information generally affects the potency of almost all optimizations which can be performed. Essentially, without precise alias information many potential optimizations will be missed or, if identified, must be ignored.
As will be apparent to those of skill in the art, there are essentially three categories of alias information that are represented in a compiler, each of which is described below. In general, alias information is symmetric (i.e.--if `x` is an alias of `y`,then `y` is also an alias of `x`),reflexive (i.e.--`x` is an alias of itself) and is transitive (i.e.--it can be shown that, if `x` is an alias for `y` and `y` is an alias for `z`,`z` is an alias of `x`). The exception to the general case of alias symmetry is `uses` of storage locations in call induced aliasing, which is discussed below in more detail. The exception to the general case of alias transitivity is structural aliasing, which is also discussed below in more detail.
Structural aliasing information comprises the situation wherein two symbols are mapped to overlying regions in memory. In many language models, structural aliasing only occurs between members of an aggregate symbol (such as a union or a structure in C) or between the members and the aggregate symbol which contains them. As mentioned above, structural induced aliases are not transitive. For example in a C union defined as
______________________________________ union{ struct{ int i; int j; } float f; }; ______________________________________
wherein i and j are mapped to adjoining locations and f is mapped to the combination of those locations, f is aliased with each of i and j but i and j are not aliased to each other.
Call induced aliasing results from the fact that a called procedure can reference storage locations which are accessible to the calling procedure. For example, a C function can modify the value of a variable defined as an extern data type in which case the function is aliased with the extern variable.
Pointer induced aliasing results from storage locations which are referenced through pointer indirection.
Typically, in at least one early stage of a compilation process, the compiler can determine alias information with reasonable precision using the rules of the language being compiled. For example, in ANSI standard C, a pointer to an integer value is precluded from pointing to a floating point value. Accordingly, a compiler can precisely determine that, for example in the code fragment above, if p has been declared as a pointer to a floating point data type and x is declared as an integer data type (which also means that y, z and q are also integer data types), then *p cannot point to x and thus they are not aliased. Similarly, x, y and z cannot be aliased with a, b or *p and the order of the last two instructions in the fragment can be reversed if desired.
It is relatively easy to obtain precise aliasing information which is based upon: language rules (eg.--a pointer to a float data type cannot point to an integer data type); language features (eg.--FORTRAN 90's TARGET attribute); or explicit assertions to the compiler made by the programmer (eg.--an ANSI C pragma that specifies that a procedure does not modify external storage locations). However, such is not the case for later stages in the compilation process. Specifically, once the compilation process proceeds beyond compiling separate compilation units, precise alias information has been difficult to obtain. As an example, it has generally not been possible to determine if a pointer in one compilation unit is aliased with a storage location in another compilation unit.
As used herein, the term "compilation unit" is intended to comprise any block of program code which is processed independently of other units of program code in the first stage of a compilation process. As used herein, the term "first stage of a compilation process" comprises the stage in the compilation process wherein the compiler is operating on language-specific instructions, rather than on instructions in a non-language specific intermediate instructions. For example, a single file of source code, a single function definition (whether defined in its own file or grouped with other function definitions in a file), etc. are compilation units. As will be apparent to those of skill in the art, compilation units can also comprise such blocks of a program which are written in different languages. For example, the user interface portions of a program may be written in C++ while mathematical functions in the program may be written in Fortran 90.
In the prior art of which the present inventor is aware, attempts to derive alias information between multiple compilation units, referred to herein as inter-compilation unit analysis, have been limited except for structural aliasing. In many circumstances, such attempts have provided no additional information and in some circumstances have resulted in the loss of alias information which was otherwise available from the earlier stages of the compilation process.
An example of a prior art attempt at improving alias information at the inter-compilation unit level is shown in U.S. Pat. No. 5,146,594 to Iitsuka. This patent teaches a technique for computing alias information for procedures which is alleged to be more precise than that obtained in the prior art. The technique discriminates between cases wherein a symbol may share storage with another symbol and cases wherein the symbol must share storage with another symbol.